//
// Created by Administrator on 2021/10/16.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        vector<vector<int>> ans;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                ans.push_back(vector<int>{i, j});
            }
        }
        sort(ans.begin(), ans.end(), [&](vector<int> a, vector<int> b) {
            return abs(a[0] - rCenter) + abs(a[1] - cCenter) < abs(b[0] - rCenter) + abs(b[1] - cCenter);
        });
        return ans;
    }
};

class Solution2 {
public:
    const int dr[4] = {1, 1, -1, -1};
    const int dc[4] = {1, -1, -1, 1};

    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int maxDist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter);
        vector<vector<int>> ret;
        int row = rCenter, col = cCenter;
        ret.push_back({row, col});
        for (int dist = 1; dist <= maxDist; dist++) {
            row--; // 到上面那一格
            for (int i = 0; i < 4; i++) {
                while ((i % 2 == 0 && row != rCenter) || (i % 2 != 0 && col != cCenter)) {
                    if (row >= 0 && row < rows && col >= 0 && col < cols) {
                        ret.push_back({row, col});
                    }
                    // 轮一圈
                    row += dr[i];
                    col += dc[i];
                }
            }
        }
        return ret;
    }
};

int main() {
    Solution2 solution;
    vector<vector<int>> ans = solution.allCellsDistOrder(2, 3, 1, 2);
    for (int i = 0; i < ans.size(); ++i) {
        for (int j = 0; j < ans[0].size(); ++j) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
